import java.util.List;

public class Test4 {
    public static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public static ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }
        ListNode cur = pHead;
        ListNode head2 = null;

        while (cur != null) {
            int data=cur.val;
            if (data<x) {
                ListNode node=new ListNode(data);
                if(head2==null){
                    head2=node;
                }else{
                    node.next=head2;
                    head2=node;
                }

            }
            cur=cur.next;
        }
        pHead=remove(pHead,x);
        head2=reverse(head2);
        ListNode pcur=head2;
        if(pcur!=null){
            while(pcur.next!=null){
                pcur=pcur.next;
            }
            pcur.next=pHead;
        }
        if(head2!=null){
            return head2;
        }else {
            return pHead;
        }

    }
    public static ListNode remove(ListNode head,int key){
        if(head==null){
            return head;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val<key){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val<key){
            head=head.next;
        }
        return head;
    }
    public static ListNode reverse(ListNode head){
        if(head==null){
            return null;
        }
        ListNode n1=null;
        ListNode n2=head;
        ListNode n3=head.next;
        while(n2!=null){
            n2.next=n1;
            n1=n2;
            n2=n3;
            if(n3!=null){
                n3=n3.next;
            }
        }
        return n1;
    }

    public static void main(String[] args) {
        ListNode n1=new ListNode(6);
        ListNode n2=new ListNode(2);
        ListNode n3=new ListNode(8);
        n1.next=n2;
        n2.next=n3;
        ListNode ret=partition(n1,9);
    }
}
